package com.leetcode.算法策略相关.动态规划;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2021/3/4
 * @description: 354. 俄罗斯套娃信封问题
 * https://leetcode-cn.com/problems/russian-doll-envelopes/
 * 没想到还可以 基于二分查找再优化
 * https://leetcode-cn.com/problems/russian-doll-envelopes/solution/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/
 */
public class C_354_俄罗斯套娃信封问题 {

	static C_354_俄罗斯套娃信封问题 action = new C_354_俄罗斯套娃信封问题();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	public static void test1() {
		int[][] envelopes = new int[][]{{5, 4}, {6, 4}, {6, 7}, {2, 3}};
		int res = action.maxEnvelopes(envelopes);
		System.out.println("res = " + res);
	}

	public static void test2() {
		int[][] envelopes = new int[][]{{46, 89}, {50, 53}, {52, 68}, {72, 45}, {77, 81}};
		int res = action.maxEnvelopes(envelopes);
		System.out.println("res = " + res);
	}


	/**
	 * 不行，这种叠罗汉的方式是有 bug 的，估计不适合两个条件的情况：
	 * 通过不了 test2
	 *
	 * @param envelopes
	 * @return
	 */
	public int maxEnvelopesBySuperposition(int[][] envelopes) {
		if (envelopes == null) {
			return 0;
		}
		int num = envelopes.length;
		if (num < 2) {
			return num;
		}
		//1.进行排序
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o2[1] - o1[1];
				} else {
					return o2[0] - o1[0];
				}
			}
		});
		//2.采用 叠罗汉的方式
		//统计每个罗汉的大小
		int[] countArr = new int[num];
		int[][] arr = new int[num][2];
		int endIndex = 0;
		for (int i = 0; i < num; i++) {
			boolean hasPlace = false;
			for (int j = 0; j < endIndex; j++) {
				if (arr[j][0] > envelopes[i][0] && arr[j][1] > envelopes[i][1]) {
					//符合要求
					hasPlace = true;
					//更新数组
					arr[j] = envelopes[i];
					countArr[j]++;
					break;
				}
			}
			if (!hasPlace) {
				arr[endIndex] = envelopes[i];
				countArr[endIndex] = 1;
				endIndex++;
			}
		}
		int max = 0;
		//遍历
		for (int i = 0; i < endIndex; i++) {
			max = Math.max(max, countArr[i]);
		}
		return max;
	}

	/**
	 * 那么我只能换一个思路了
	 * 通过 DP 的方式
	 * 状态方程：
	 * i 处的元素最多能套的娃 的数量= 往前数符合条件的最多的套娃数量
	 *
	 * @param envelopes
	 * @return
	 */
	public int maxEnvelopes(int[][] envelopes) {
		if (envelopes == null) {
			return 0;
		}
		int num = envelopes.length;
		if (num < 2) {
			return num;
		}
		//1.进行排序
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o2[1] - o1[1];
				} else {
					return o2[0] - o1[0];
				}
			}
		});
		//2. DP 处理
		int[] dp = new int[num];
		dp[0] = 1;
		for (int i = 1; i < num; i++) {
			int max = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (envelopes[j][0] > envelopes[i][0] && envelopes[j][1] > envelopes[i][1]) {
					max = Math.max(max, dp[j] + 1);
				}
//				if (j == 0) {
//					break;
//				} else if (envelopes[j][1] <= envelopes[j - 1][1]) {
//					break;
//				}
			}
			dp[i] = max;
		}

		int res= dp[0];
		for (int i = 1; i < num; i++) {
			res = Math.max(res, dp[i]);
		}
		return res;

	}
}
